package leetcode.easy.q70;

public class Q{
    public static void main(String[] args) {
        System.out.printf(new Solution().climbStairs(4)+"");
    }
}
/**
斐波那契
 思考：
 n格楼梯
 第一步一格：剩n-1格楼梯
 第一步二格：剩n-2格楼梯
 f(n)=q(第一步一格)+q(第一步2格)
     =f(n-1)+f(n-2)
*/
class Solution {
    public int climbStairs(int n) {
        //1格楼梯，1种
        //2格楼梯，2种
        //3格楼梯，3种,第一步1格的方法数（#2）+第一步2格的方法数(#1)
        //4格楼梯，5种,第一步1格的方法数（#3）+第一步2格的方法数(#2)
        //...
        //dp[i]=dp[i-1]+dp[i-2]
        int[] dp=new int[n];
        if(n<=2){
            return n;
        }
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i<n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];

    }
}